package org.raymond.iworks.study.basic.structure.tree.b;

/**
 * 二叉树的问题分析
 * 二叉树需要加载到内存,如果二叉树的节点少,没什么问题,但是如果节点非常多,比如1亿个,就有问题
 * 1) 在构建二叉树时,需要多次进行I/O操作(海量数据存在数据库或文件中).
 * 节点海量,构建二叉树时,速度有影响.
 * 2) 节海量,也会造成二叉树高度很高,降低操作速度.
 *
 * 多叉树
 * 1) 在二叉树中,每个节点有数据项,最多有两个子节点.如果允许每个节点可以有更多的数据项
 * 和更多的子节点,就是多叉树(multiway tree)
 * 2) 2-3树,2-3-4树就是多叉树.多叉树通过重新组织节点,减少树的高度,能对二叉树进行优化
 * 3) 下面的2-3树就是一颗多叉树. []表示一个节点中的数据项
 *               [16]
 *    [8  12]          [27]
 * [7] [10]  [14]   [17]  [29]
 * --------------   ----------
 *      3节点           2节点
 * 节点[8 12]有3个子节点[7],[10],[14]
 *
 * B树的介绍
 * B树通过重新组织节点,降低树的高度,并且减少i/o读写次数来提升效率
 *                                  []->[]->[]
 * []->[]->[]->[]->[] []->[]->[]->[]->[] []->[]->[]->[]->[] []->[]->[]->[]->[]
 * 1) 如上图,B树通过重新组织节点,降低树的高度
 * 2) 文件系统及数据库系统的设计者利用来磁盘预读原理,将一个节点的大小设为等于一个页
 * (页的大小通常为4k),这样每个节点只需要一次IO就可以完全载入
 * 3) 将树的度(最大的节点的分支数)M设置为1024,在600亿(1024的4次方为1万亿)个元素中
 * 最多只需要4次IO操作就可以读取到想要的元素,B树广泛应用于文件存储系统以及数据库系统中
 *
 * 2-3树基本介绍
 * 2-3树是简单的B树结构,特点:
 * 1) 2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)
 * 2) 有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点
 * 注:2节点指一个左节点和一个右节点,只有一个数据项.
 * 3) 有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点
 * 注:3节点指一个左节点,一个中节点和一个右节点,有两个数据项.
 * 4) 2-3树是由二节点和三节点构成的树
 *
 * 详细说明:所有二叉树的节点最多只有2个子节点,我们把这种节点称做2-节点.它跟二叉树的节点
 * 一样,左孩子的值小于根节点的值,右孩子的值大于等于根孩子的值.同理,3-节点就是指最多只有
 * 3个子节点的节点,而每个节点最多可以存放两个值.假设根节点的两个值分别是v1,v2.左中右
 * 3个孩子节点的值分别是l,m,r.那么它们之间的关系就为 l<v1<=m<=v2<=r.所以,2-3树就是
 * 指由2-节点和(或)3-节点共同构成的树.
 *
 * 2-3树应用案例
 * 将数列{16,24,12,32,14,26,34,10,8,28,38,20}构建成2-3树,并保证数据插入的
 * 大小顺序.
 *             [16]
 *      [12]              [26 32]
 * [8 10] [14]     [20 24] [28] [34 38]
 * 插入规则:
 * 1) 2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)
 * 2) 有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点
 * 3) 有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点
 * 4) 当按照规则插入一个树到某个节点时,不能满足上面三个要求,就需要拆,
 * 先向上拆,如果上层满,则拆本层,拆后仍然需要满足上面3个条件
 * 5) 对于三节点的子树的值大小仍然遵守(BST二叉排序树)的规则
 *
 * 构建步骤:
 * 数列{16,24,12,32,14,26,34,10,8,28,38,20} 中的数依次逐个加入树
 * [16]   [16] [24]      [16]          [16]
 *                    [12]  [24]   [12]   [24 32]
 * ---
 *        [16]                 [16    26]              [16    26]
 * [12 14]    [24 32]   [12 14]   [24]   [32]   [12 14]   [24]   [32 34]
 * ---
 *             [16    26]                          [16]
 *     [12]       [24]   [32 34]   ===>    [12]            [26]
 * [10]    [14]                        [10]    [14]    [24]    [32 34]
 * 说明:
 * 1,当插入10时,应当在12-14这个节点上插入，但是12-14已经满了,因此向上看,16-26也满了
 * 2,因此将10-12-14拆成 10<-12->14,因为其他拆法,不能满足二节点或三节点
 * 3,但是,这时,叶子节点没有全部在同一层,需要调整 16-26,将26调整到下面
 * 待参考:慕课网 bobo老师
 *               [16]
 *       [12]            [26]
 * [8 10]    [14]    [24]    [32 34]
 *-----
 *               [16]
 *       [12]            [26    32]
 * [8 10]    [14]    [24]   [28]   [34]
 * -----
 *               [16]
 *       [12]            [26    32]
 * [8 10]    [14]    [24]   [28]   [34 38]
 * ------
 *               [16]
 *       [12]               [26    32]
 * [8 10]    [14]    [20 24]   [28]   [34 38]
 *
 * 2-3-4树
 * 1) 有四个子节点的节点叫四节点,四节点要么没有子节点,要么有四个子节点
 * 注:4节点指一个左节点,两个中节点和一个右节点,有三个数据项.
 * 2) 其他与3节点一致
 *
 * B树的介绍
 * B-tree树即B树, B即Balanced,平衡的意思.有人把B-tree翻译成B-树,容易让人误解。
 * 实际上,B-树就是B树
 * 2-3树和2-3-4树就是B树
 * B树的说明:
 * 1) B树的阶:节点的最多子节点个数,比如2-3树的阶是3,2-3-4树的阶是4
 * 2) B树的搜索,从根节点开始,对节点内的关键字(有序)序列进行二分查找,如果命中则结束,
 * 否则进入查询关键字所属范围的儿子节点;重复,直到所对应的儿子指针为空,或已经是叶子节点
 * 3) 关键字集合分布在整棵树中,即叶子节点和非叶子节点都存放数据(关键字就在这些节点里)
 * 4) 搜索有可能在非叶子节点结束
 * 5) 其搜索性能等价于在关键字全集内做一次二分查找
 *
 * B+树的介绍
 * B+树是B树的变体,也是一种多路搜索树
 * 1) B+树的搜索与B树基本相同,区别是B+树只有达到叶子节点才会命中(B树可以在非叶子节点命中),
 * 其性能也等价于在关键字全集做一次二分查找
 * 2) 所有关键字都出现在叶子节点的链表中(即数据只能在叶子节点(也叫稠密索引)),且链表中
 * 的关键字(数据)恰好是有序的
 * 3) 不可能在非叶子节点命中
 * 4) 非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层.
 * 5) 更适合文件索引系统
 * 6) B树和B+树各有自己的应用场景,不能说B+树完全比B树好.反之亦然.
 *
 * 对B+树的理解:
 * 所有数据都存入一个链表,然后将链表中所有数据的取值范围切割为树中的节点.以提高查询效率.
 *
 * B*树的介绍
 * B*树是B+树的变体,在B+树的非根和非叶子节点再增加指向兄弟的指针.
 * B*树的说明:
 * 1) B*树定义了非叶子节点关键字个数至少为(2/3)*M,即块的最低使用率为2/3,而B+树的
 * 块的最低使用率为B*树的1/2
 * 2) 从第一个特点我们可以看出,B*树分配新节点的概率比B+树要低,空间使用率更高
 *
 */
public class BTreeDemo {
    public static void main(String[] args) {

    }
}
